package jp.aist.gtrc.plus.admission.EDF;

import java.util.*;

import jp.aist.gtrc.plus.admission.*;
import jp.aist.gtrc.plus.admission.EDF.*;

public class EDFAdmission {

   /*
    * The cpu states may change after calling test(). Thus, be sure to restore
    *  the original states.
    */
   public boolean test(Collection<CPU> cpus, Collection<Job> jobs) {
      Job[] sortedJobs = jobs.toArray(new Job[jobs.size()]);
      Arrays.sort(sortedJobs, new DeadlineComparator());

      TreeSet<CPU> sortedCPUs = new TreeSet<CPU>(new LoadComparator());
      sortedCPUs.addAll(cpus);

      for (Job job : sortedJobs) {
         CPU minCPU = sortedCPUs.first();
         sortedCPUs.remove(minCPU);

         minCPU.lastOccupied = minCPU.lastOccupied + job.exeTime; // execute job on this cpu
         if (minCPU.lastOccupied > job.deadline) {
//            System.out.println("EDFAdmission rejects new job since job " + job.name + " deadline " + job.deadline + " is violated. (to be completed at " + minCPU.lastOccupied + ")");
            return false;
         }

         sortedCPUs.add(minCPU);
      }
         
      return true;
   }

   /*
    * return 0 if accepted, otherwise the recommended deadline.
    *
    * The cpu states may change after calling this method. Thus, be sure to restore
    *  the original states.
    */
   public int testAndRecommend(Collection<CPU> cpus, Collection<Job> admittedJobs, JobArray newJobArray) throws AdmissionException {
      ArrayList<Job> admittedJobList = new ArrayList<Job>(admittedJobs);
      Collections.sort(admittedJobList, new DeadlineComparator());

      int id = admittedJobList.size();
      int firstNewJobId = id;
      int lastNewJobId = id;
      ArrayList<Job> newJobs = new ArrayList<Job>();
      for (int i=0; i < newJobArray.numOfJobs; i++) {
           Job job = new Job(id,newJobArray.name+"/"+i,newJobArray.exeTime,newJobArray.deadline);
           newJobs.add(job);
           lastNewJobId = id;
           id++;  // id of each new job is incremental at the last id
      }
      ArrayList<Job> sortedJobs = new ArrayList<Job>(admittedJobList);
      insertAfter(sortedJobs,newJobs,newJobArray.deadline);

      TreeSet<CPU> sortedCPUs = new TreeSet<CPU>(new LoadComparator());
      sortedCPUs.addAll(cpus);
   
      int newDeadline = newJobArray.deadline;
      TreeSet<CPU> savedSortedCPUs = null;
      int save_i = 0;
      boolean found = false;

      while (!(found) && (save_i <= admittedJobs.size())) {
         int i = 0;
         boolean isScheduled = false;
        
         for (i=save_i; i < sortedJobs.size(); i++) {
            Job job = sortedJobs.get(i);
            if (job.id == firstNewJobId) {
               // do checkpointing 
               savedSortedCPUs = cloneSortedCPUs(sortedCPUs);
               save_i = i;
            }

            CPU minCPU = sortedCPUs.first();
            sortedCPUs.remove(minCPU);

            minCPU.lastOccupied = minCPU.lastOccupied + job.exeTime; // execute job on this cpu
            if (job.id >= firstNewJobId) {
               // find the completion time for the new job array
               if (minCPU.lastOccupied > newDeadline) {
                  newDeadline = minCPU.lastOccupied;
               }
               if (job.id == lastNewJobId) isScheduled = true;

            } else {
               if (minCPU.lastOccupied > job.deadline) {
//                  System.out.println("EDFAdmission rejects new job " + job.name + " since deadline " + job.deadline + " is violated. (to be completed at " + minCPU.lastOccupied + ")");
                  if (!isScheduled) {
                     throw new AdmissionException("Invalid precondition in " + job.name + " since deadline is missed by " + (minCPU.lastOccupied - job.deadline) + " sec.");
                  }

                  /*
                   * trying to find the new completion time for the new job array
                   */
                  // re-insert new job array after the last violated jobs
                  sortedJobs = new ArrayList<Job>(admittedJobList);
                  insertAfter(sortedJobs,newJobs,job.deadline);
                  sortedCPUs = savedSortedCPUs;
//                  System.out.println("redo");
                  break; // redo testing again from the last checkpoint
               }
            }
   
//            System.out.println("put job " + job.id + " " + job.name + " on " + minCPU.id + " until " + minCPU.lastOccupied + " < " + job.deadline);
            sortedCPUs.add(minCPU);
         }
         
         if (i == sortedJobs.size()) found = true;
      }

      if (newDeadline == newJobArray.deadline) {
         return 0;
      } else {
         //System.out.println("Recommended deadline = " + newDeadline);
         return newDeadline;
      }

   }

   /*
    * Assume newJobs is sorted by id.
    */
   private void insertAfter(ArrayList<Job> sortedJobs, ArrayList<Job> newJobs, int afterTime) {
      int position = sortedJobs.size();
      for (int i=0; i < sortedJobs.size(); i++) {
         Job job = sortedJobs.get(i);
         if (afterTime < job.deadline) {
            position = i;
            break;
         }
      }
//      System.out.println("Insert new jobs at position " + position);
      sortedJobs.addAll(position,newJobs);
   }

   private TreeSet<CPU> cloneSortedCPUs(TreeSet<CPU> sortedCPUs) {
      TreeSet<CPU> clone = new TreeSet<CPU>(new LoadComparator());
      Iterator<CPU> it = sortedCPUs.iterator();
      while (it.hasNext()) {
         CPU cpu = it.next();
         //System.out.println("Checkpoint cpu " + cpu.id + " : " + cpu.lastOccupied);
         clone.add(new CPU(cpu));
      }
      return clone;
   }

}
